import java.util.ArrayList;
import java.util.List;

/**
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description: https://leetcode.cn/problems/house-robber-iii/ 337 打家劫舍
 * @date 2023/03/11
 **/
public class HouseRobberIII {

    class Solution {
        public int rob(TreeNode root) {
            List<Integer> values = new ArrayList();
            hepler(root, values);
            if (values.isEmpty()) {
                return 0;
            }
            if (values.size() == 1) {
                return values.get(0);
            }
            // dp[i][0] 第 i 家不打劫的最大收益
            // dp[i][1] 第 i 家打劫时的最大收益
            int[][] dp = new int[values.size()][2];
            dp[0][0] = 0;
            dp[0][1] = values.get(0);
            int maxProfit = dp[0][1];
            for (int i = 1; i < values.size(); i++) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
                dp[i][1] = dp[i - 1][0] + values.get(i);
                maxProfit = Math.max(dp[i][0], dp[i][1]);
            }
            return maxProfit;
        }

        private void hepler(TreeNode root, List<Integer> res) {

            if (root == null) {
                return;
            }

            hepler(root.left, res);

            res.add(root.val);

            hepler(root.right, res);
        }
    }


    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}



